﻿/**
 * @file tree.c
 * @author septem (jsm920@outlook.com)
 * @brief @see tree.h
 * @version 0.0.1
 * @date 2024-10-06
 * 
 * @copyright Copyright (c) 2024
 * 
 */
#include "tree.h"

#if defined(_WIN32) && defined(_MSC_VER)
// #pragma execution_character_set("utf-8")
#define WIN32_LEAN_AND_MEAN // 预处理器宏定义，它告诉编译器仅包含Windows SDK中最常用的函数和数据类型，从而减小编译时间和生成的可执行文件大小。
#include <stdio.h>
#include <stdlib.h>
#include <string.h> // memcpy() memset()
#include <assert.h>
#elif defined(__linux__)
#include <stdio.h>
#include <stdlib.h> //malloc() realloc() free()
#include <string.h> // memset() memcpy() memmove()
#include <assert.h> // assert()
#endif

btreeiterator_t* BtreeIteratorInit(btree_t* pbt, btreenode_t* pbtn)
{
    btreeiterator_t* _pbti = malloc(sizeof(btreeiterator_t));
    if(_pbti == NULL || (NULL == (_pbti->pstack = (btreenode_t**)malloc((sizeof(btreenode_t*) * BTREEMAXLEVEL)))))
    {
        if(_pbti) {free(_pbti);}
        return NULL;
    }
    _pbti->pbt = pbt;
    // _pbti->level =0;
    // _pbti->top = 0;
    _pbti->cntCapacity = BTREEMAXLEVEL;
    _pbti->pstack[0] = pbtn?pbtn:pbt->pbtnRoot; _pbti->top=1;
    return _pbti;
}

void BtreeIteratorUninit(btreeiterator_t* pbti)
{
    if(pbti)
    {
        if(pbti->pstack){free(pbti->pstack);pbti->pstack = 0;}
        free(pbti);
    }
}
/**
 * @brief 向btreeiterator_t* 栈中压入一个数据
 * 
 * @param pbti 
 * @param node 
 * @return btreenode_t* 
 */
btreenode_t* _BtreeIteratorStackPush(btreeiterator_t* pbti, btreenode_t* node)
{
    if(pbti->top >= pbti->cntCapacity)
    {
        btreenode_t** pstackTmp = (btreenode_t**)realloc(pbti->pstack, sizeof(btreenode_t*) * ( pbti->cntCapacity + BTREEMAXLEVEL));
        if(pstackTmp == NULL)
        {
            return NULL;
        }
        pbti->pstack = pstackTmp;
        pbti->cntCapacity += BTREEMAXLEVEL;
    }
    pbti->pstack[pbti->top] = node;
    pbti->top++;
    return node;
}
/**
 * @brief 从btreeiterator_t* 栈中弹出一个数据
 * 
 * @param pbti 
 */
btreenode_t* _BtreeIteratorStackPop(btreeiterator_t* pbti)
{
    if(pbti->top ) {pbti->top--; return pbti->pstack[pbti->top];}
    return NULL;
}
/**
 * @brief 从btreeiterator_t* 栈移除第0个数据(当做队列使用)
 * 
 * @param pbti 
 * @return btreenode_t* 
 */
btreenode_t* _BtreeIteratorStackShift(btreeiterator_t* pbti)
{
    btreenode_t* _pbtn = NULL;
    if(pbti->top > 1 ) 
    {
        _pbtn = pbti->pstack[0];
        memmove(&pbti->pstack[0],&pbti->pstack[1], sizeof(btreenode_t*)*(pbti->top-1));
        pbti->top--;
    }
    else if(pbti->top == 1)
    {
        _pbtn = pbti->pstack[0];
        pbti->top--;
    }
    return _pbtn;
}


/**
 * @brief 返回btreeiterator_t* 栈顶指针
 * 
 * @param pbti 
 * @return btreenode_t* 
 */
btreenode_t* _BtreeIteratorStackTop(btreeiterator_t* pbti)
{
    return pbti->top ? pbti->pstack[pbti->top-1]: NULL;
}

/**
 * @brief 从栈顶为0(0就是pbti->top-1)开始计算获取指针
 * 
 * @param pbti 
 * @param pos 
 * @return btreenode_t* 
 */
btreenode_t* _BtreeIteratorStackPos(btreeiterator_t* pbti, unsigned int pos)
{
    return pos + 1 < pbti->top ? pbti->pstack[pbti->top-1 - pos]: NULL;
}

btreeiterator_t* BtreeIteratorTraversalPreorder(btreeiterator_t* pbti, BtreeTraversalCallback op, void* param)
{
    btreenode_t* _pbtn;
    if(pbti->top == 0) // 如果栈是空的, 压入根元素
    {   
        _pbtn = pbti->pbt->pbtnRoot;
    }
    else
    {
        _pbtn = pbti->pstack[pbti->top-1]; pbti->top--;
    }
    BtreeTraversalCallback_t bttc;
    while (_pbtn != NULL || pbti->top > 0) //当栈上有对象
    {
        while (_pbtn != NULL)
        {
            bttc.node = _pbtn;
            if( 0 > op(_pbtn->data,param, &bttc))
            {
                return pbti;
            }
            if(NULL == _BtreeIteratorStackPush(pbti, _pbtn))
            {
                return NULL;
            }
            _pbtn = _pbtn->pbtnl; 
        }
        _pbtn = _BtreeIteratorStackPop(pbti);
        _pbtn = _pbtn->pbtnr; 
    }
    return pbti;
}

btreeiterator_t* BtreeIteratorTraversalInorder(btreeiterator_t* pbti, BtreeTraversalCallback op, void* param)
{
    btreenode_t* _pbtn;
    if(pbti->top == 0) // 如果栈是空的, 压入根元素
    {   
        _pbtn = pbti->pbt->pbtnRoot;
    }
    else
    {
        _pbtn = pbti->pstack[pbti->top-1]; pbti->top--;
    }
    BtreeTraversalCallback_t bttc;
    while (_pbtn != NULL || pbti->top > 0) //当栈上有对象
    {
        while (_pbtn != NULL)
        {
            if(NULL == _BtreeIteratorStackPush(pbti, _pbtn))
            {
                return NULL;
            }
            _pbtn = _pbtn->pbtnl;
        }
        _pbtn = _BtreeIteratorStackPop(pbti);
        bttc.node = _pbtn;
        if( 0 > op(_pbtn->data,param,&bttc))
        {
            return pbti;
        }
        _pbtn = _pbtn->pbtnr;
    }
    return pbti;
}

btreeiterator_t* BtreeIteratorTraversalPostorder(btreeiterator_t* pbti, BtreeTraversalCallback op, void* param)
{
    btreenode_t* _pbtn;
    if(pbti->top == 0) // 如果栈是空的, 压入根元素// push 两次用于判断是否经过节点
    {   
        _pbtn = pbti->pbt->pbtnRoot;    
        pbti->pstack[0] = _pbtn;pbti->pstack[1] = _pbtn; pbti->top=2;
    }
    else
    {
        _pbtn = pbti->pstack[pbti->top-1]; pbti->pstack[pbti->top] =_pbtn; pbti->top++;
    }
    BtreeTraversalCallback_t bttc;
    while ( pbti->top > 0) //当栈上有对象
    {
        _pbtn = _BtreeIteratorStackPop(pbti);
        if(pbti->top > 0 && _pbtn == _BtreeIteratorStackTop(pbti))
        {
            if(_pbtn->pbtnr != NULL)
            {
                if(NULL == _BtreeIteratorStackPush(pbti, _pbtn->pbtnr) || NULL == _BtreeIteratorStackPush(pbti, _pbtn->pbtnr)) // push 两次用于判断是否经过节点
                {
                    return NULL;
                }
            }
            if(_pbtn->pbtnl != NULL)
            {
                if(NULL == _BtreeIteratorStackPush(pbti, _pbtn->pbtnl) || NULL == _BtreeIteratorStackPush(pbti, _pbtn->pbtnl)) 
                {
                    return NULL;
                }
            }
        }
        else
        {
            bttc.node = _pbtn;
            if( 0 > op(_pbtn->data,param,&bttc))
            {
                return pbti;
            }
        }
    }
    return pbti;
}



btreeiterator_t* BtreeIteratorTraversalLevelorder(btreeiterator_t* pbti, BtreeTraversalCallback op, void* param)
{
    if(pbti->top == 0) // 如果栈是空的, 压入根元素
    {   
        pbti->pstack[0] = pbti->pbt->pbtnRoot;pbti->top=1; 
    }
    unsigned int topOrigin = pbti->top;
    unsigned int level = 0; // 层数
    unsigned int levelBeg = pbti->top-1; // 每一层第一个压入栈开始的的位置
    unsigned int top = pbti->top;
    BtreeTraversalCallback_t bttc;
    while (1)
    {
        unsigned int topTmp = top;
        for(unsigned int i = levelBeg; i != top; i++) 
        {
            bttc.node = pbti->pstack[i];
            bttc.level = 0;
            if( 0 > op(pbti->pstack[i]->data,param,&bttc)) // 处理前面的元素
            {
                return pbti;
            }
            // 将前面元素的子元素夺栈
            if(pbti->pstack[i]->pbtnl)
            {
                if(NULL == _BtreeIteratorStackPush(pbti, pbti->pstack[i]->pbtnl) ) 
                {
                    return NULL;
                }
            }
            if(pbti->pstack[i]->pbtnr)
            {
                if(NULL == _BtreeIteratorStackPush(pbti, pbti->pstack[i]->pbtnr) ) 
                {
                    return NULL;
                }
            }
        }
        if(top < pbti->top) // top 变化说明有压栈 有子元素
        {
            level++;
            levelBeg = topTmp;
            top = pbti->top;
        }
        else
        {
            // 不再有子元素，跳出
            break;
        }
    }
    // 恢复栈
    pbti->top = topOrigin;
    return pbti;
}

btree_t* BtreeMalloc(unsigned int szElem, unsigned int cnt)
{
    unsigned int _szMem = BtreeMemUsed(szElem, cnt);
    btree_t* _pbt = (btree_t*)malloc(_szMem);
    if(_pbt == NULL)
    {
        return NULL;
    }
    if(NULL == BtreeInit(_pbt,szElem,cnt))
    {
        free(_pbt);
        return NULL;
    }
    // Array2Push(&_pbt->stackToFree, (void*)(&_pbt));
    return _pbt;
}
void BtreeFree(btree_t* pbt)
{
    if(pbt)
    {
        BtreeUninit(pbt);
        free(pbt);        
    }
}

btree_t* BtreeInit(btree_t* pbt, unsigned int szElem, unsigned int cnt)
{
    pbt->szNode = roundup(szElem + sizeof(btreenode_t), sizeof(void*));
    pbt->pbtnRoot = (btreenode_t*)((char*)pbt + sizeof(btree_t));
    pbt->pbtnRoot->pbtnl = NULL;pbt->pbtnRoot->pbtnr = NULL;pbt->pbtnRoot->pbtnp = NULL;
    pbt->pbtnPrealloc = (btreenode_t*)((char*)pbt->pbtnRoot + pbt->szNode);
    pbt->cntCapacity = cnt;
    pbt->szElem = szElem;
    pbt->cntGrow = cnt;
    memset(pbt->pbtb, 0, sizeof(btreeblock_t) * BTREEDEFAULTCNTBLOCK);
    pbt->pbtbM = 0;
    pbt->cntPBTBM = 0;
    btreenode_t* _pbtnPrev = pbt->pbtnPrealloc; // 当前的前一个
    btreenode_t* _pbtn = _pbtnPrev;
    for(unsigned int i = 0; i < cnt; i ++, _pbtn = (btreenode_t*)((char*)_pbtn + pbt->szNode))
    {
        _pbtnPrev->pbtnr = _pbtn; _pbtn->pbtnl = NULL; _pbtnPrev = _pbtn;_pbtn->pbtnp = NULL;
    }
    _pbtnPrev->pbtnr = NULL;pbt->pbtnPrealloc->pbtnl = NULL;
    return pbt;
}
void BtreeUninit(btree_t* pbt)
{
    btreeblock_t* _pbtb = pbt->pbtb;
    for(int i = 0; _pbtb[i] != NULL &&i != BTREEDEFAULTCNTBLOCK; i++)
    {
        free(_pbtb[i]);_pbtb[i] = NULL;
    }
    if(pbt->pbtbM) 
    {
        _pbtb = pbt->pbtbM;
        for(int i = 0; _pbtb[i] != NULL &&i != pbt->cntPBTBM; i++)
        {
            free(_pbtb[i]);_pbtb[i] = NULL;
        }
        free(pbt->pbtbM); pbt->pbtbM = NULL; pbt->cntPBTBM = 0;
    }
}
int BtreeRealloc(btree_t* pbt, unsigned int grow)
{
    grow = (grow < pbt->cntGrow ? pbt->cntGrow: grow);
    btreenode_t* _pbtn = malloc(pbt->szNode * grow);
    if(_pbtn == NULL)
    {
        return -1;
    }
    if(pbt->pbtbM == NULL) 
    {
        for(int i = 0; i != BTREEDEFAULTCNTBLOCK; i++)
        {
            if(pbt->pbtb[i] == NULL)
            {
                pbt->pbtb[i] = _pbtn; 
                break;
            }
        }
        if(_pbtn == NULL)
        { 
            pbt->pbtbM = (btreeblock_t *)malloc(sizeof(btreeblock_t) * BTREEDEFAULTCNTBLOCK); 
            if(pbt->pbtbM == NULL)
            {
                free(_pbtn);
                return -1;
            }
            pbt->cntPBTBM = BTREEDEFAULTCNTBLOCK;
            memset(pbt->pbtbM, 0, sizeof(btreeblock_t) * BTREEDEFAULTCNTBLOCK);
            pbt->pbtbM[0] =  _pbtn;
        }
    }
    else
    {
        btreeblock_t * pbtb = pbt->pbtbM;
        for(int i = 0; i != pbt->cntPBTBM; i++)
        {
            if(pbtb[i] == NULL)
            {
                pbtb[i] = _pbtn;
                break;
            }
        }
        if(_pbtn == NULL)
        {
            btreeblock_t* pbtbTmp = (btreeblock_t*)realloc(pbt->pbtbM,sizeof(btreeblock_t) * (pbt->cntPBTBM+BTREEDEFAULTCNTBLOCK));
            if(pbtbTmp == NULL)
            {
                free(_pbtn);
                return -1;
            }
            memset( (char*)pbtbTmp + sizeof(btreeblock_t)*pbt->cntPBTBM, 0, sizeof(btreeblock_t)* BTREEDEFAULTCNTBLOCK);
            pbt->pbtbM = pbtbTmp;
            pbt->pbtbM[pbt->cntPBTBM] = _pbtn; 
            pbt->cntPBTBM += BTREEDEFAULTCNTBLOCK;
        }
    }
    pbt->cntCapacity += grow;
    btreenode_t* pbtnPrev = _pbtn; // 当前的前一个
    btreenode_t* pbtn = _pbtn;
    for(unsigned int i = 0; i < grow ; i ++, pbtn = (btreenode_t*)((char*)pbtn + pbt->szNode))
    {
        pbtnPrev->pbtnr = pbtn; pbtn->pbtnl = NULL; pbtnPrev = _pbtn;
    }
    pbtnPrev->pbtnr = pbt->pbtnPrealloc?pbt->pbtnPrealloc :NULL;
    pbt->pbtnPrealloc = _pbtn; pbt->pbtnPrealloc->pbtnl = NULL;
    return 0;
}

btreenode_t* BtreeRoot(btree_t* pbt)
{
    return pbt->pbtnRoot;
}

btreenode_t* BtreeNodeParent(btreenode_t* node)
{
    return node->pbtnp;
}

btreenode_t* BtreeNodeLeft(btreenode_t* node)
{
    return node->pbtnl;
}

btreenode_t* BtreeNodeRight(btreenode_t* node)
{
    return node->pbtnr;
}

btreenode_t* BtreeNodeSetLeft(btree_t* pbt, btreenode_t* node, void* data)
{
    assert(node != NULL);
    if(node->pbtnl == NULL)
    {
        if(pbt->pbtnPrealloc == NULL)
        {
            if(-1 == BtreeRealloc(pbt, pbt->cntGrow))
            {
                return NULL;
            }
        }
        pbt->cntElem ++;
        node->pbtnl = pbt->pbtnPrealloc;
        pbt->pbtnPrealloc = pbt->pbtnPrealloc->pbtnr;
        node->pbtnl->pbtnl = NULL;
        node->pbtnl->pbtnr = NULL;
        node->pbtnl->pbtnp = node;
    }
    if(data)
    {
        memcpy(node->pbtnl->data,data, pbt->szElem);
    }
    return node->pbtnl;
}

btreenode_t* BtreeNodeSetRight(btree_t* pbt, btreenode_t* node, void* data)
{
    assert(node != NULL);
    if(node->pbtnr == NULL)
    {
        if(pbt->pbtnPrealloc == NULL)
        {
            if(-1 == BtreeRealloc(pbt, pbt->cntGrow))
            {
                return NULL;
            }
        }
        pbt->cntElem ++;
        node->pbtnr = pbt->pbtnPrealloc;
        pbt->pbtnPrealloc = pbt->pbtnPrealloc->pbtnr;
        node->pbtnr->pbtnl = NULL;
        node->pbtnr->pbtnr = NULL;
        node->pbtnr->pbtnp = node;
    }
    if(data)
    {
        memcpy(node->pbtnr->data,data, pbt->szElem);
    }
    return node->pbtnr;
}

/**
 * @brief 先序遍历Proorder Traversal (current-left-right)(竞然可以正常工作，还没搞懂原因)
 * 
 * @param node 
 * @param op 
 * @param params 
 * @return btreenode_t* 
 */
btreenode_t* _BtreeTraversalPreorder(btreenode_t* node, int (*op)(void* data,void* params), void* params)
{
    btreenode_t* _pbtn = node;
    btreenode_t* _pbtnParent = node->pbtnp;
    btreenode_t* _pbtnPre = NULL; //当从子元素退回时需要记录在此
    #ifndef NDEBUG
    int kkk = 0;
    #endif
    while (_pbtn != _pbtnParent) // 向子元素叫前进//回到父元素叫退回
    {
        #ifndef NDEBUG
        kkk++; if(kkk > 1000000){assert(0);} //调试时防止死循环
        #endif
        if(_pbtnPre == NULL) // 表示非退回的，所以执行 op
        {
            if(0 > op(_pbtn->data, params))
            {
                return _pbtn;
            }
            if(_pbtn->pbtnl) // 向左子元素前进
            {
                _pbtn = _pbtn->pbtnl;
            }
            else if(_pbtn->pbtnr) // 向右子元素前进
            {
                _pbtn = _pbtn->pbtnr;
            }
            else
            { // 左子元素和右子元素都是空的，退回
                _pbtnPre = _pbtn; _pbtn = _pbtn->pbtnp;
            }
        }
        else //是由子元素退回的
        {
            if(_pbtnPre == _pbtn->pbtnl) //是由左子元素退回的
            {
                if(_pbtn->pbtnr) // 向右子元素前进
                {
                    _pbtn = _pbtn->pbtnr;_pbtnPre=NULL;
                }
                else //右子元素为空
                {
                    _pbtnPre = _pbtn; _pbtn = _pbtn->pbtnp;
                }
            }
            else if(_pbtnPre == _pbtn->pbtnr) //是由右子元素退回的
            { //再次退回
                _pbtnPre = _pbtn; _pbtn = _pbtn->pbtnp;
            }
        }
    }
    return node;
}
/**
 * @brief Inorder Traversal (left-current-right):
 * 
 * @param node 
 * @param op 
 * @param params 
 * @return btreenode_t* 
 */
btreenode_t* _BtreeTraversalInorder(btreenode_t* node, int (*op)(void* data,void* params), void* params)
{
    btreenode_t* _pbtn = node;
    btreenode_t* _pbtnParent = node->pbtnp;
    btreenode_t* _pbtnPre = NULL; //当从子元素退回时需要记录在此
    #ifndef NDEBUG
    int kkk = 0;
    #endif
    while (_pbtn != _pbtnParent) // 向子元素叫前进//回到父元素叫退回
    {
        #ifndef NDEBUG
        kkk++; if(kkk > 1000000){assert(0);} //调试时防止死循环
        #endif
        if(_pbtnPre == NULL) // 表示非退回的，所以执行 op
        {
            if(_pbtn->pbtnl) // 向左子元素前进
            {
                _pbtn = _pbtn->pbtnl;
            }
            else if(_pbtn->pbtnr) // 向右子元素前进
            {
                if(0 > op(_pbtn->data, params)) // 父元素没有左子元素 执行op
                {
                    return _pbtn;
                }
                _pbtn = _pbtn->pbtnr;
            }
            else
            { // 左子元素和右子元素都是空的，退回
                if(0 > op(_pbtn->data, params)) // 左右都没有节点 执行op
                {
                    return _pbtn;
                }
                _pbtnPre = _pbtn; _pbtn = _pbtn->pbtnp;
            }
        }
        else //是由子元素退回的
        {
            if(_pbtnPre == _pbtn->pbtnl) //是由左子元素退回的
            {
                if(0 > op(_pbtn->data, params)) // 由左子元素退回的父元素,执行op
                {
                    return _pbtn;
                }
                if(_pbtn->pbtnr) // 向右子元素前进
                {
                    _pbtn = _pbtn->pbtnr;_pbtnPre=NULL;
                }
                else //右子元素为空
                {
                    _pbtnPre = _pbtn; _pbtn = _pbtn->pbtnp;
                }
            }
            else if(_pbtnPre == _pbtn->pbtnr) //是由右子元素退回的
            { //再次退回
                _pbtnPre = _pbtn; _pbtn = _pbtn->pbtnp;
            }
        }
    }
    return node;
}
/**
 * @brief Postorder Traversal (left-right-current)
 * 
 * @param node 
 * @param op 
 * @param params 
 * @return btreenode_t* 
 */
btreenode_t* _BtreeTraversalPostorder(btreenode_t* node, int (*op)(void* data,void* params), void* params)
{
    btreenode_t* _pbtn = node;
    btreenode_t* _pbtnParent = node->pbtnp;
    btreenode_t* _pbtnPre = NULL; //当从子元素退回时需要记录在此
    #ifndef NDEBUG
    int kkk = 0;
    #endif
    while (_pbtn != _pbtnParent) // 向子元素叫前进//回到父元素叫退回
    {
        #ifndef NDEBUG
        kkk++; if(kkk > 1000000){assert(0);} //调试时防止死循环
        #endif
        if(_pbtnPre == NULL) // 表示非退回的，所以执行 op
        {
            if(_pbtn->pbtnl) // 向左子元素前进
            {
                _pbtn = _pbtn->pbtnl;
            }
            else if(_pbtn->pbtnr) // 向右子元素前进
            {
                _pbtn = _pbtn->pbtnr;
            }
            else
            { // 左子元素和右子元素都是空的，退回
                if(0 > op(_pbtn->data, params))
                {
                    return _pbtn;
                }
                _pbtnPre = _pbtn; _pbtn = _pbtn->pbtnp;
            }
        }
        else //是由子元素退回的
        {
            if(_pbtnPre == _pbtn->pbtnl) //是由左子元素退回的
            {
                if(_pbtn->pbtnr) // 向右子元素前进
                {
                    _pbtn = _pbtn->pbtnr;_pbtnPre=NULL;
                }
                else //右子元素为空
                {
                    if(0 > op(_pbtn->data, params))
                    {
                        return _pbtn;
                    }
                    _pbtnPre = _pbtn; _pbtn = _pbtn->pbtnp;
                }
            }
            else if(_pbtnPre == _pbtn->pbtnr) //是由右子元素退回的
            { //再次退回
                if(0 > op(_pbtn->data, params))
                {
                    return _pbtn;
                }
                _pbtnPre = _pbtn; _pbtn = _pbtn->pbtnp;
            }
        }
    }
    return node;
}
/**
 * @brief Level Order Traversal 使用栈保存所有节点指针来遍历
 * 
 * @param node 
 * @param op 
 * @param params 
 * @return btreenode_t* 
 */
btreenode_t* _BtreeTraversalLevelorder(btreenode_t* node, int (*op)(void* data,void* params), void* params)
{
    #ifndef NDEBUG
    int kkk = 0;
    #endif
    unsigned int cntMalloc = LEVEL_ORDER_TRAVERSAL;
    btreenode_t** parray = (btreenode_t**)malloc(sizeof(btreenode_t*)* cntMalloc);
    if(parray == NULL)
    {
        return NULL;
    }
    parray[0] = node;
    unsigned int top = 1; // 当前使用的parray数量
    unsigned int level = 0; // 层数
    unsigned int levelBeg = top-1; // 每一层第一个压入栈开始的的位置
    unsigned int topBack = top;
    while (1)
    {
        #ifndef NDEBUG
        kkk++; if(kkk > 1000000){assert(0);} //调试时防止死循环
        #endif
        unsigned int topTmp = top;
        for(unsigned int i = levelBeg; i != topBack; i++) 
        {
            if( 0 > op(parray[i]->data,params)) // 处理前面的元素
            {
                free(parray);return parray[i];
            }
            // 将前面元素的子元素夺栈
            if(parray[i]->pbtnl)
            {
                if(top >= cntMalloc)
                {
                    btreenode_t** parrayTmp = (btreenode_t**)realloc( parray, sizeof(btreenode_t*)* cntMalloc*2);
                    if(parrayTmp == NULL)
                    {
                        free(parray);return NULL;
                    }
                    cntMalloc *= 2;
                    parray = parrayTmp;
                }
                parray[top++] =  parray[i]->pbtnl;
            }
            if(parray[i]->pbtnr)
            {
                if(top >= cntMalloc)
                {
                    btreenode_t** parrayTmp = (btreenode_t**)realloc( parray, sizeof(btreenode_t*)* cntMalloc*2);
                    if(parrayTmp == NULL)
                    {
                        free(parray);return NULL;
                    }
                    cntMalloc *= 2;
                    parray = parrayTmp;
                }
                parray[top++] =  parray[i]->pbtnr;
            }
        }
        if(topBack < top) // top 变化说明有压栈 有子元素
        {
            level++;
            levelBeg = topTmp;
            topBack = top;
        }
        else
        {
            // 不再有子元素，跳出
            break;
        }
    }
    free(parray);
    return node;
}
btreenode_t* BtreeTraversal(btreenode_t* node, int (*op)(void* data,void* params), void* params, int mode)
{
    typedef btreenode_t* (*_fun)(btreenode_t*, int (*)(void* data,void* params), void* );
    _fun _FUN[]={_BtreeTraversalPreorder,_BtreeTraversalInorder,_BtreeTraversalPostorder,_BtreeTraversalLevelorder};
    assert(mode < (int)(sizeof(_FUN)/sizeof(_FUN[0])));
    return _FUN[mode](node, op, params);
}

tree_t* TreeMalloc(unsigned int szElem, unsigned int cnt)
{
    return BtreeMalloc(szElem, cnt);
}
void TreeFree(tree_t* pt)
{
    BtreeFree((btree_t*)pt);
}
tree_t* TreeInit(tree_t* pt, unsigned int szElem, unsigned int cnt)
{
    return BtreeInit((btree_t*)pt, szElem, cnt);
}
void TreeUninit(tree_t* pt)
{
    BtreeUninit((btree_t*)pt);
}

int TreeRealloc(tree_t* pt, unsigned int cnt)
{
    return BtreeRealloc((btree_t*)pt, cnt);
}

treenode_t* TreeRoot(tree_t* pt)
{
    return (treenode_t*)BtreeRoot((btree_t*)pt);
}

treenode_t* TreeNodeParent(treenode_t* node)
{
    return (treenode_t*)BtreeNodeParent(node);
}

treenode_t* TreeNodeChild(treenode_t* node)
{
    return (treenode_t*)BtreeNodeLeft((btreenode_t*)node);
}

treenode_t* TreeNodeNext(treenode_t*node)
{
    return (treenode_t*)BtreeNodeRight((btreenode_t*)node);
}

treenode_t* TreeNodePrev(treenode_t*node)
{
    treenode_t* parent = (treenode_t*)BtreeNodeParent(node);
    treenode_t* b = (treenode_t*)BtreeNodeLeft((btreenode_t*)node);
    treenode_t* p= NULL;
    while (b != node)
    {
        p = b;
        b = (treenode_t*)BtreeNodeRight((btreenode_t*)node);
    }
    return p;
}

treenode_t* TreeNodeSet(tree_t* pt, treenode_t* node, void* data)
{
    memcpy(node->data,data, pt->szElem );
    return node;
}

treenode_t* TreeNodeCreate(tree_t* pt, void* data)
{
    if(pt->pbtnPrealloc == NULL && (-1 == TreeRealloc(pt, 0)))
    {
        return NULL;
    }
    treenode_t* _node = pt->pbtnPrealloc; pt->pbtnPrealloc=pt->pbtnPrealloc->pbtnr; pt->cntElem ++;
    if(data)
    {
        memcpy(_node->data,data, pt->szElem);
    }
    #ifndef NDEBUG
    _node->pbtnp = NULL;_node->pbtnr = NULL;_node->pbtnl = NULL;
    #endif
    return _node;
}
int _TreeNodeDel_Callback(void* data, void*params, TreeTraversalCallback_t *pttc)
{
    tree_t* pt = (tree_t*)params;
    treenode_t* node = pttc->node;
    node->pbtnr = pt->pbtnPrealloc;pt->pbtnPrealloc=node;
    return 0;
}

void TreeNodeDel(tree_t* pt, treenode_t* node)
{
    //
    if(node!= pt->pbtnRoot )
    {
        if(node->pbtnp)
        {
            treenode_t* b = node->pbtnp;
            treenode_t* p = NULL;
            while (b != node)
            {
                p = b;
                b = b->pbtnr;
            }
            if(p == NULL)
            {
                node->pbtnp->pbtnl = node->pbtnr;
            }
            else
            {
                p->pbtnr = node->pbtnr;
            }            
        }
        TreeTraversal( node, _TreeNodeDel_Callback,  pt);
    }
    else 
    {
        treenode_t* child = node->pbtnl;
        while (child)
        {
            TreeTraversal( child, _TreeNodeDel_Callback,  pt);
            child = child->pbtnr;
        }
    }
}

treenode_t* TreeNodeAddChild(tree_t* pt, treenode_t* node, treenode_t* child)
{
    if(node == NULL){node = pt->pbtnRoot;}
    child->pbtnp = node;child->pbtnr = NULL;child->pbtnl = NULL;
    if(node->pbtnl) // node 有子节点
    {
        treenode_t* brother = node->pbtnl;
        treenode_t* r = brother->pbtnr;
        while (r)
        {
            brother = r;
            r = r->pbtnr;
        }
        brother->pbtnr = child;
    }
    else
    {
        node->pbtnl = child;
    }
    return child;
}

treenode_t* TreeNodeAddChild2(tree_t* pt, treenode_t* node, void* data)
{
    treenode_t* child = TreeNodeCreate(pt,data);
    return child?TreeNodeAddChild(pt, node, child):NULL;
}

treenode_t* TreeNodeAddChildren(tree_t* pt, treenode_t* node, void* data, unsigned int cnt)
{
    treenode_t* _ptn = TreeNodeCreate(pt, data);
    if(_ptn == NULL) {return NULL;}

    if(_ptn && cnt> 1 && \
        NULL ==TreeNodeAddBrothers(pt, _ptn, (char*)data + pt->szElem,cnt-1))
    {
        return NULL;
    }
    return _ptn;
}

treenode_t* TreeNodeInsertBefore(tree_t* pt, treenode_t* node, treenode_t* brother)
{
    assert(node != NULL);
    brother->pbtnp = node; brother->pbtnl = NULL;
    treenode_t* parent = node->pbtnp;
    treenode_t* b = parent->pbtnl;
    treenode_t* p = NULL;
    while (b != node)
    {
        p = b;
        b = b->pbtnr;
    }
    if(p == NULL)
    {
        brother->pbtnr = parent->pbtnl;parent->pbtnl=brother;
    }
    else
    {
        brother->pbtnr = b; p->pbtnr = brother;
    }
    return brother;
}
treenode_t* TreeNodeAddBrothers(tree_t* pt, treenode_t* node, void* data, unsigned int cnt)
{
    // treenode_t* _ptn = TreeNodeAddBrother(pt,node, data);
    // treenode_t* _ptntmp = _ptn;
    // for(unsigned int i = 1; _ptntmp && i < cnt; i++)
    // {
    //     _ptntmp = TreeNodeAddBrother(pt, _ptntmp, (char*)data + i * pt->szElem);
    // }
    // return _ptntmp?_ptn:NULL;
    return NULL;
}

treenode_t* TreeTraversal( treenode_t* node, TreeTraversalCallback callback, void* params )
{
    #ifndef NDEBUG
    int kkk = 0;
    #endif
    unsigned int cntMalloc = LEVEL_ORDER_TRAVERSAL;
    btreenode_t** parray = (btreenode_t**)malloc(sizeof(btreenode_t*)* cntMalloc);
    if(parray == NULL)
    {
        return NULL;
    }
    parray[0] = node;
    unsigned int top = 1; // 当前使用的parray数量
    unsigned int level = 0; // 层数
    unsigned int levelBeg = top-1; // 每一层第一个压入栈开始的的位置
    unsigned int topBack = top;
    TreeTraversalCallback_t ttc;
    while (1)
    {
        #ifndef NDEBUG
        kkk++; if(kkk > 1000000){assert(0);} //调试时防止死循环
        #endif
        unsigned int topTmp = top;
        for(unsigned int i = levelBeg; i != topBack; i++) 
        {
            treenode_t* child = parray[i]->pbtnl; // 子元素
            ttc.node = parray[i];
            ttc.level = level;
            if( 0 > callback(parray[i]->data,params, &ttc)) // 处理前面的元素
            {
                free(parray);return parray[i];
            }
            while (child)
            {
                if(top >= cntMalloc)
                {
                    btreenode_t** parrayTmp = (btreenode_t**)realloc( parray, sizeof(btreenode_t*)* cntMalloc*2);
                    if(parrayTmp == NULL)
                    {
                        free(parray);return NULL;
                    }
                    cntMalloc *= 2;
                    parray = parrayTmp;
                }
                parray[top++] =  child;
                child = child->pbtnr;
            }
        }
        if(topBack < top) // top 变化说明有压栈 有子元素
        {
            level++;
            levelBeg = topTmp;
            topBack = top;
        }
        else
        {
            // 不再有子元素，跳出
            break;
        }
    }
    free(parray);
    return 0;
}